import re
import struct

class Parser:
    def __init__(self,code):
        self.token_regex = re.compile("(\\(|\\)|#t|#f|\\d+\\.\\d+|[\\+\\-]?\\d+|>=|<=|>|<|=|'|`|\"([^\"]|\\\\|\\\")*\"|[^\\s\\(\\)\"']+)",re.M)
        self.tokens = self.token_regex.findall(code)

    def tokenizer(self):
        return [i[0] for i in self.tokens]


class Syntax:
    def __init__(self,tokens):
        self.tokens = tokens

    def parse(self):
        stack =[]
        for token in self.tokens:
            if token==')':
                tmp = stack.pop()
                l = []
                while tmp!='(':
                    l.insert(0,tmp)
                    tmp = stack.pop()
                stack.append(l)
            else:
                stack.append(token)
        return stack


class generater:
    def __init__(self,ast):
        self.ast = ast
        self.macro={}
        self.letexpand(self.ast)
        #print(self.ast)

    def lookup(self,var,env):
        i = 0
        tmp = env
        while True:
            if var in tmp:
                return [i,tmp[var]]
            else:
                i = i + 1
                if 'up' in tmp:
                    tmp=tmp['up']
                else:
                    break;
        return None
    def letexpand(self,ast):
        if type(ast) == type([]):
            if len(ast) >0 and type(ast[0]) != type([]):
                if ast[0] == 'let':
                    args = []
                    values = []
                    self.letexpand(ast[2])
                    body = ast[2]
                    for i in ast[1]:
                        args.append(i[0])
                        values.append(i[1])
                    tmp = [['lambda' , args ,body]] + values
                    for i in range(0,len(ast)):
                        ast.pop()
                    for i in tmp:
                        ast.append(i)
                else:
                    for i in range(0,len(ast)):
                        self.letexpand(ast[i])
            else:
                for i in range(0,len(ast)):
                    self.letexpand(ast[i])
        else:
            pass
    def macroset(self,ast):
        '''(define-syntax foo
    (syntax-rules ()
      [(_ a ...)
       (printf "~a\n" (list a ...))
       ]
       ))
'''
        if type(ast) == type([]) :
            if ast[0] == 'define-syntax':
                name = ast[1]
                self.macro[name] = ast[2][2:]
                ast.clear()
            else:
                for i in range(0,len(ast)):
                    self.macroset(ast[i])
        pass
    def expand(self,ast,args):
        if type(ast) == type([]) :
            for i in range(0,len(ast)):
                ast[i] = self.expand(ast[i],args)
            return ast
        else:
            if ast in args:
                return args[ast]
            else:
                return ast
        
    def macroexpand(self,ast):
        if type(ast) == type([]):
            for i in range(0,len(ast)):
                    if type(ast[i]) == type([]):
                        if len(ast[i])==0:
                            continue
                        if type(ast[i][0]) == type('') and ast[i][0] in self.macro:
                            #print(ast[i])
                            for macro in self.macro[ast[i][0]]:
                                if len(ast[i]) == len(macro[0]):
                                    args = {}
                                    for n in range(0,len(macro[0])):
                                        args[macro[0][n]] = ast[i][n]
                                    ast[i] = self.expand(macro[1],args)
                                    break
                        else:
                            self.macroexpand(ast[i])
        pass
    def gen(self):
        env = {}
        code = []
        for i in self.ast:
            code = code+self._gen(i,env)
        code.append('STOP')
        return code
    
    def _gen(self,ast,env,othercall=True):
        result = []
        if type(ast) == type([]) and len(ast) > 0:
            if type(ast[0]) == type([]):
                result.append('NIL')
                for i in range(1,len(ast)):
                    #result.append(self._gen(ast[i],env))
                    result=result+self._gen(ast[i],env)
                    result.append('CONS')
                #result.append(self._gen(ast[0],env))
                result=result+self._gen(ast[0],env)
                result.append('AP')
            else:
                if ast[0] == 'lambda':
                    result.append('LDF')
                    subenv = {}
                    subenv['up'] = env
                    if len(ast[1]) > 0:
                        for var in ast[1]:
                            subenv[var] = len(subenv) - 1
                    tmp = self._gen(ast[2],subenv,False)
                    tmp.append('RTN')
                    result.append(tmp)
                elif ast[0] == 'begin':
                    i=1
                    while i<len(ast):
                        result=result+self._gen(ast[i],env,othercall)
                        i+=1
                elif ast[0] == 'if':
                    result=result+self._gen(ast[1],env,othercall)
                    result.append('SEL')
                    left = self._gen(ast[2],env,othercall)
                    left.append('JOIN')
                    result.append(left)
                    right = self._gen(ast[3],env,othercall)
                    right.append('JOIN')
                    result.append(right)
                elif ast[0] == 'define':
                    result.append('LDN')
                    result.append(ast[1])
                    result=result+self._gen(ast[2],env,othercall)
                    result.append('DEF')
                elif ast[0] == '=':
                    result=result+self._gen(ast[1],env,True)
                    result=result+self._gen(ast[2],env,True)
                    result.append('EQ')
                elif ast[0] == '>':
                    result=result+self._gen(ast[1],env,True)
                    result=result+self._gen(ast[2],env,True)
                    result.append('GT')
                elif ast[0] == '<':
                    result=result+self._gen(ast[1],env,True)
                    result=result+self._gen(ast[2],env,True)
                    result.append('LT')
                elif ast[0] == '>=':
                    result=result+self._gen(ast[1],env,True)
                    result=result+self._gen(ast[2],env,True)
                    result.append('GE')
                elif ast[0] == '<=':
                    result=result+self._gen(ast[1],env,True)
                    result=result+self._gen(ast[2],env,True)
                    result.append('LE')
                elif ast[0] == '+':
                    result.append('NIL')
                    for i in range(1,len(ast)):
                        result=result+self._gen(ast[i],env,True)
                        result.append('CONS')
                    result.append('ADD')
                elif ast[0] == '-':
                    result.append('NIL')
                    for i in range(1,len(ast)):
                        result=result+self._gen(ast[i],env,True)
                        result.append('CONS')
                    result.append('SUB')
                elif ast[0] == '*':
                    result.append('NIL')
                    for i in range(1,len(ast)):
                        result=result+self._gen(ast[i],env,True)
                        result.append('CONS')
                    result.append('MUL')
                elif ast[0] == '/':
                    result.append('NIL')
                    for i in range(1,len(ast)):
                        result=result+self._gen(ast[i],env,True)
                        result.append('CONS')
                    result.append('DIV')
                elif ast[0] == '%':
                    result.append('NIL')
                    for i in range(1,len(ast)):
                        result=result+self._gen(ast[i],env,True)
                        result.append('CONS')
                    result.append('MOD')
                else:
                    result.append('NIL')
                    for i in range(1,len(ast)):
                        #result.append(self._gen(ast[i],env))
                        result=result+self._gen(ast[i],env,True)
                        result.append('CONS')
                    #result.append('LDF')
                    #result.append(ast[0])
                    l = self.lookup(ast[0],env)
                    if l:
                        result.append('LD')
                        result.append(l)
                    else:
                        result.append('LDFN')
                        result.append(ast[0])
                    if othercall:
                        result.append('AP')
                    else:
                        result.append('TAP')
            
        else:
            if len(ast) > 0:
                if ast.find('\'')>=0:
                    result.append('LDSY')
                    result.append(ast)
                elif ast.find('"')>=0:
                    result.append('LDS')
                    result.append(ast)
                elif ast.isnumeric():
                    
                    if ast.find('.')>=0:
                        result.append('LDD')
                        result.append(float(ast))
                    else:
                        result.append('LDI')
                        result.append(int(ast))
                else:
                    
                    l = self.lookup(ast,env)
                    if l:
                        result.append('LD')
                        result.append(l)
                    else:
                        result.append('LDN')
                        result.append(ast)
        return result

def add(vm,args):
    ret = 0
    for i in args:
        ret = ret + i
    return ret
  
class SecdVm:
    def __init__(self,ast):
        self.stack = []
        self.env = [{}]
        self.code = []
        self.dump = []
        #self.registGlobal('+',add)
    def registGlobal(self,name,func):
        #self.env[0][name] = func
        pass
    def op_ldc(self):
        self.code.pop(0)
        data = self.code.pop(0)
        self.stack.append(data)
        pass
    def op_ld(self):
        self.code.pop(0)
        position = self.code.pop(0)
        if type(position) == type([]):
            self.stack.append(self.env[len(self.env) - 1 - position[0]][position[1]])
        else:
            self.stack.append(self.env[0][position])
    def op_cons(self):
        self.code.pop(0)
        data = self.stack.pop()
        self.stack[len(self.stack)-1].append(data)
        pass
    def op_nil(self):
        self.code.pop(0)
        self.stack.append([])
        pass
    def op_add(self):
        self.code.pop(0)
        args = self.stack.pop()
        data = 0
        for i in args:
            data = data + i
        self.stack.append(data)
    def op_def(self):
        self.code.pop(0)
        value = self.stack.pop()
        name = self.stack.pop()
        self.env[0][name] = value
    def op_sub(self):
        self.code.pop(0)
        args = self.stack.pop()
        data = args[0]
        for i in args[1:]:
            data = data - i
        self.stack.append(data)
    def op_mul(self):
        self.code.pop(0)
        args = self.stack.pop()
        data = args[0]
        for i in args[1:]:
            data = data * i
        self.stack.append(data)
    def op_eq(self):
        self.code.pop(0)
        right = self.stack.pop()
        left = self.stack.pop()
        data = left == right
        self.stack.append(data)
    def op_gt(self):
        self.code.pop(0)
        right = self.stack.pop()
        left = self.stack.pop()
        data = left > right
        self.stack.append(data)
    def op_lt(self):
        self.code.pop(0)
        right = self.stack.pop()
        left = self.stack.pop()
        data = left < right
        self.stack.append(data)
    def op_ge(self):
        self.code.pop(0)
        right = self.stack.pop()
        left = self.stack.pop()
        data = left >= right
        self.stack.append(data)
    def op_le(self):
        self.code.pop(0)
        right = self.stack.pop()
        left = self.stack.pop()
        data = left <= right
        self.stack.append(data)
    def op_div(self):
        self.code.pop(0)
        args = self.stack.pop()
        data = args[0]
        for i in args[1:]:
            data = data / i
        self.stack.append(data)
    def op_mod(self):
        self.code.pop(0)
        args = self.stack.pop()
        data = args[0] % args[1]
        self.stack.append(data)
    def op_ap(self):
        self.code.pop(0)
        func = self.stack.pop()
        args = self.stack.pop()
        if type(func) ==type([]):
            self.dump.append({
                'stack':self.stack,
                'code':self.code,
                'env':self.env
                })
            self.code = func
            self.env.append(args)
        else:
            data = func(self,args)
            self.stack.append(data)

    def op_rtn(self):
        self.code.pop(0)
        data = self.stack.pop()
        dump = self.dump.pop()
        self.stack = dump['stack']
        self.code = dump['code']
        self.env = dump['env']
        self.stack.append(data)
        pass
    def op_ldf(self):
        self.code.pop(0)
        func  = self.code.pop(0)
        if type(func)==type([]):
            self.stack.append(func)
        else:
            func = self.env[0][func]
            self.stack.append(func)
    def op_sel(self):
        self.code.pop(0)
        left  = self.code.pop(0)
        right  = self.code.pop(0)
        data = self.stack.pop()
        self.dump.append(self.code)
        if data:
            self.code = left
        else:
            self.code = right
    def op_join(self):
        self.code.pop(0)
        code  = self.dump.pop()
        self.code = code
    def run(self,opcode):
        self.code=opcode
        while True:
            command = self.code[0]
            if command == 'LDC':#
                self.op_ldc()
            elif command == 'LD':#
                self.op_ld()
            elif command == 'LDF':#
                self.op_ldf()
            elif command == 'NIL':#
                self.op_nil()
            elif command == 'STOP':#
                break
            elif command == 'CONS':#
                self.op_cons()
            elif command == 'AP':#
                self.op_ap()
            elif command == 'RTN':#
                self.op_rtn()
            elif command == 'ADD':#
                self.op_add()
            elif command == 'SUB':#
                self.op_sub()
            elif command == 'DIV':#
                self.op_div()
            elif command == 'MUL':#
                self.op_mul()
            elif command == 'MOD':#
                self.op_mod()
            elif command == 'SEL':#
                self.op_sel()
            elif command == 'JOIN':#
                self.op_join()
            elif command == 'EQ':#
                self.op_eq()
            elif command == 'GT':#
                self.op_gt()
            elif command == 'LT':#
                self.op_lt()
            elif command == 'GE':#
                self.op_ge()
            elif command == 'LE':#
                self.op_le()
            elif command == 'DEF':#
                self.op_def()

class compiler:
    def __init__(self,il):
        self.il = il
        self.magic = b'secd'
        self.data = b''
        self.length = 0
        self.start = 0
        self.code = b''
        self.instructions = {
            'add':0x01,
            'sub':0x02,
            'div':0x03,
            'mul':0x04,
            'mod':0x05,
            'ld':0x06,
            'ldi':0x07,
            'ldd':0x08,
            'lds':0x09,
            'ldc':0x0a,
            'ldsy':0x0b, 
            'ldb':0x0c, 
            'ldv':0x0d, 
            'ldf':0x0e,
            'ap':0x0f,
            'rtn':0x10,
            'nil':0x11,
            'cons':0x12,
            'sel':0x13,
            'join':0x14,
            'eq':0x15,
            'gt':0x16,
            'lt':0x17,
            'ge':0x18,
            'le':0x19,
            'def':0x1a,
            'stop':0x1b,
            'ldn':0x1c,
            'ldfn':0x1d,
            'dum':0x1e,
            'rap':0x1f,
            'rec':0x20,
            'tap':0x21
    }

    def _prepare(self,code):
        length = len(code)
        i = 0
        ret = b''
        while i < length:
            if type(code[i]) == type([]):
                sublist = self._prepare(code[i])
                ret = ret + struct.pack('i',len(sublist))+sublist
            else:
                ret = ret + struct.pack('h',self.instructions[code[i].lower()]) 
                if code[i] =='LDS':
                    position = len(self.data)
                    ls = code[i+1].encode('utf8')
                    self.data = self.data+struct.pack('i',len(ls))+ls
                    ret = ret + struct.pack('i',position)
                    i = i + 1
                elif code[i] =='LDSY':
                    position = len(self.data)
                    ls = code[i+1].encode('utf8')
                    self.data = self.data+struct.pack('i',len(ls))+ls
                    ret = ret + struct.pack('i',position)
                    i = i + 1
                elif code[i] =='LDN':
                    position = len(self.data)
                    ls = code[i+1].encode('utf8')
                    self.data = self.data+struct.pack('i',len(ls))+ls
                    ret = ret + struct.pack('i',position)
                    i = i + 1
                elif code[i] =='LDD':
                    ret = ret +  struct.pack('f',code[i+1])
                    i = i + 1
                elif code[i] =='LDI':
                    print(code[i+1])
                    ret = ret + struct.pack('i',code[i+1])
                    i = i + 1
                elif code[i] =='LD':
                    ret = ret + struct.pack('ii',code[i+1][0],code[i+1][1])
                    i = i + 1
                elif code[i] =='SEL':
                    sublist = self._prepare(code[i+1])
                    ret = ret + struct.pack('i',len(sublist))+sublist
                    i = i + 1
                    sublist = self._prepare(code[i+1])
                    ret = ret + struct.pack('i',len(sublist))+sublist
                    i = i + 1
                elif code[i] =='LDFN':
                    position = len(self.data)
                    ls = code[i+1].encode('utf8')
                    self.data = self.data+struct.pack('i',len(ls))+ls
                    ret = ret + struct.pack('i',position)
                    i = i + 1
                elif code[i] =='LDF':
                    sublist = self._prepare(code[i+1])
                    print(len(sublist))
                    ret = ret + struct.pack('i',len(sublist))+sublist
                    i = i + 1
                else:
                    pass
            i = i + 1
        return ret
    
    def to_binary(self):
        magic = b'secd'#magic
        bins = self._prepare(self.il);
        bins = self.data + bins
        length = len(bins)
        position = len(self.data)
        return magic+struct.pack('i',length)+struct.pack('i',position)+bins
    
        
        
               
p = Parser('''((lambda (x) (+ x 1)) 2)''')
#p = Parser('''((lambda (x) (if (= x 1) 1 (+ 1 (rec (- x 1))))) 10)''')
syntax = Syntax(p.tokenizer())
s=syntax.parse()
g = generater(s)
g.macroset(g.ast)
g.macroexpand(g.ast)
il = g.gen()
#vm = SecdVm(il)
#vm.run(il)
print(il)
c=compiler(il)

#bi=c.to_binary()
#with open("G:\\secdvm\\test.bin",'wb') as fp:
#    fp.write(bi)
